class MedianFinder {

    Queue<Integer> A,B;
    /** initialize your data structure here. */
    public MedianFinder() {
        //小根堆(存从小到大)保存较大的一半,堆顶是最小的
        A = new PriorityQueue<>();
        //大根堆(存从大存到小)保存较小的一半,堆顶是最大的
        B = new PriorityQueue<>((x, y) -> (y - x));
    }
    public void addNum(int num) {
        //往A里插
        if(A.size() == B.size()) {
            //先往B里插
            B.add(num);
            //然后取B的堆顶元素
            A.add(B.poll());
        }else {
            //往B里插
            A.add(num);
            B.add(A.poll());
        }
    }
    
    public double findMedian() {
        if(A.size() == B.size()) {
            return A.peek() - (A.peek() - B.peek())/2.0;
        }else {
            return A.peek();
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */